// m

// 给定一棵二叉树的根节点root和一个整数目标targetSum
// 要求找出所有从根节点到叶子节点 路径总和等于给定目标和targetSum的路径

// 解题思路：回溯求解，在回溯的同时，记录下当前路径，同时维护targetSum，每遍历到一个 节点，就减去该节点值，如果遇到叶子节点，并且targetSum === 0，将当前路径加入
// 到答案数组中，然后递归遍历左右子树，并回退当前节点，继续遍历

function pathSum(root, targetSum) {
    let res = []
    let path = []

    function dfs(root, targetSum) {
        if (!root) {
            return
        }
        path.push(root.val)
        targetSum -= root.val
        if (!root.left && !root.right && targetSum === 0) {
            res.push(path.slice(0))
        }
        dfs(root.left, targetSum)
        dfs(root.right, targetSum)
        path.pop()
    }
    dfs(root, targetSum)
    return res
}

const root = {
    val: 1,
    left: {
        val: 2,
        left: null,
        right: {
            val: 3,
            left: {
                val: 4,
                left: null,
                right: null
            },
            right: null
        },
    },
    right: {    
        val: 2,
        left: {
            val: 4,
            left: null,
            right: {
                val: 3,
                left: null,
                right: null
            }
        },
        right: null
    },
};
console.log(pathSum(root, 10))

function pathSum2(root, target) {
    let res = []
    let path = []
    function dfs(root, target) {
        if (!root) {
            return
        }
        path.push(root.val)
        if (!root.left && !root.right && target - root.val === 0) {
            res.push([...path]) 
        }
        dfs(root.left, target - root.val)
        dfs(root.right, target - root.val)
        path.pop()
    }
    dfs(root, target)
    return res
}

console.log(pathSum2(root, 10))